package leetcode.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

//402. 移掉 K 位数字
public class RemoveKdigits {
    public static void main(String[] args) {
        System.out.println(removeKdigits("10001",4));

    }

    public static String removeKdigits(String num, int k) {
        if (num.length()==k){
            return "0";
        }
        Stack<Integer> stack = new Stack<>();
        for (int i=0;i<num.length();i++){
            int ch = Integer.parseInt(num.substring(i, i + 1));
            while (k!=0 && !stack.empty() && stack.peek()>ch){
                stack.pop();
                k--;
            }
            if(ch==0 && stack.size() == 0)  {
                continue;
            }
            stack.push(ch);
        }
        StringBuilder res = new StringBuilder();
        ArrayList<Integer> list = new ArrayList<>();
        while (stack.size()!=0){

            list.add(stack.pop());
        }
        Collections.reverse(list);
        int step = list.size()-k<1?0:list.size()-k;
        for (int x :list){
            res.append(x);
        }
        String s = res.toString().substring(0, step);
        return s.length()==0?"0":s;
    }

    public static String removeKdigits2(String num, int k) {
        if(num.length() == k)       return "0";

        StringBuilder stack = new StringBuilder();


        for(int i = 0; i < num.length(); i++){
            char ch = num.charAt(i);
            while(k > 0 && stack.length() != 0 && stack.charAt(stack.length() - 1) > ch){
                stack.setLength(stack.length() - 1);
                k--;
            }
            if(ch == '0' && stack.length() == 0)    continue;

            stack.append(ch);
        }
        String result = stack.substring(0,stack.length()-k <1 ?0:stack.length()-k).toString();
        return result.length() == 0 ? "0" : result;
    }
}


